;solution to euler 14

;notes - slow
;add hashtable of previous results to speed up
;(defparameter *h* (make-hash-table))

(defun graph-build ()
	(let ((visited 0) (latest 1) (active (list 1)) cur)
		(loop
			(setf cur active)
			(loop
				(when (not cur) (return))
				(when (< (car cur) 1000000) 
					(incf visited) 
					(setf latest (car cur)))
				(when (and (= (mod (car cur) 6) 4) (/= 4 (car cur)))
					(push (/ (- (car cur) 1) 3) active))
				(setf (car cur) (* 2 (car cur)))
				(setf cur (cdr cur)))
			(format t "~a~%" visited)
			(when (>= visited 100000) (return)))
		(return-from graph-build latest)))


(defun count-chain (n)
	(let ((count 1))
		(loop 
			(when (= n 1) (return))
			(if (evenp n)
				(setf n (/ n 2))
				(setf n (+ (* 3 n) 1)))
			(incf count))
		(return-from count-chain count)))
		

;(defun solve-euler14 ()
;	(format t "Euler 14:~a" (graph-build)))
		
(defun solve-euler14 ()
	(let ((maxl 0) val n)
		(loop for i from 2 to 1000000 do
			 (when (= 0 (mod i 100000)) (format t "~a~%" i))
			(setf val (count-chain i))
			(when (> val maxl) (setf maxl val) (setf n i)))
		(format t "Euler 24:~a" n)))